/*
 * @lc app=leetcode id=52 lang=cpp
 *
 * [52] N-Queens II
 */
class Solution {
public:
    int totalNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        int cnt = 0;
        solveNQueens(n, 0, board, cnt);   
        return cnt;
    }
    void solveNQueens(int n, int c, vector<string>& board, int& cnt) {

        if (n == c) {
            cnt++;
            return ;
        }

        for (int r=0; r<n; r++) {
            if (isPosSafe(r, c, board)) {
                board[r][c] = 'Q'; 
                solveNQueens(n, c+1, board, cnt);
                board[r][c] = '.'; 
            }
        }
    }

    bool isPosSafe(int r, int c, vector<string>& board) {
        int len = board.size();
        if (r >= len || c >= len) {
            return false;
        }

        for (int i=0; i<len; i++) {
            if (board[r][i]!='.') {
                return false;
            }
        }

        for (int i=0; i<len; i++) {
            if (board[i][c]!='.') {
                return false;
            }
        }

        for (int i=r, j=c; i<len&&i>=0&&j<len&&j>=0; i++,j++) {
            if (board[i][j]!='.') {
                return false;
            }
        }
        for (int i=r, j=c; i<len&&i>=0&&j<len&&j>=0; i--,j--) {
            if (board[i][j]!='.') {
                return false;
            }
        }
        for (int i=r, j=c; i<len&&i>=0&&j<len&&j>=0; i++,j--) {
            if (board[i][j]!='.') {
                return false;
            }
        }
        for (int i=r, j=c; i<len&&i>=0&&j<len&&j>=0; i--,j++) {
            if (board[i][j]!='.') {
                return false;
            }
        }
        return true;
    }

};

